package main

import (
	"fmt"
	"image/color"
	"math/rand"
)

type Map struct {
	w, h      int8    // 宽高，默认10*10
	score     uint16  // 当前得分
	stars     []Star  // 当前星星，二维转一维存储 w*h
	clear     []Point // 上一状态消除的星星
	childrens []*Map  // 全部子状态
	parent    *Map    // 父状态
}

func (m *Map) Init() {
	for i := range m.h {
		for j := range m.w {
			m.stars[i*m.w+j] = Star(rand.Intn(5)) + 1
		}
	}
}

func (m *Map) Load(stars any) {
	n := int(m.w * m.h)
	switch v := stars.(type) {
	case []Star:
		copy(m.stars, v)
	case []byte:
		t := make([]Star, 0, n)
		for i, c := range v {
			if i >= n {
				break
			}
			if s, ok := ParseStar(c); ok {
				t = append(t, s)
			}
		}
		m.Load(t)
	case string:
		m.Load([]byte(v))
	case []color.Color:
		t := make([]Star, 0, n)
		for i, c := range v {
			if i >= n {
				break
			}
			t = append(t, ParseStarFromColor(c))
		}
		m.Load(t)
	default:
		m.Init()
	}
}

func (m *Map) Clone() *Map {
	ret := &Map{w: m.w, h: m.h, stars: make([]Star, m.w*m.h), parent: m}
	copy(ret.stars, m.stars)
	return ret
}

// Dump 打印地图
func (m *Map) Dump() {
	stars := make([]Star, m.w*m.h)
	if m.parent != nil {
		copy(stars, m.parent.stars)
		for _, c := range m.clear {
			stars[c.y*m.w+c.x] = StarNone
		}
	}
	for i := range m.h {
		if m.parent != nil {
			for j := range m.w {
				if stars[i*m.w+j] == m.parent.stars[i*m.w+j] {
					fmt.Print(m.parent.stars[i*m.w+j].Star())
				} else {
					fmt.Print(m.parent.stars[i*m.w+j].Star(true))
				}
			}
			fmt.Print(" | ")
		}
		for j := range m.w {
			fmt.Print(m.stars[i*m.w+j].Star())
		}
		fmt.Println()
	}
}

// GenerateChildrens 生成所有可能的子状态 目前测试了三种策略
// 1. 从上到下，从左到右，的顺序。可以很快找到较优解，但主要靠奖励分，没有大片区域连消，上限较低。
// 2. 剩余每种颜色平方和+当前消除数量平方*权重。综合效果较好，但某些情况下可能分数不高。
// 3. 完全随机，多试几次，总能找到较优解。
func (m *Map) GenerateChildrens() {
	visited := make(map[Point]bool)
	m.childrens = make([]*Map, 0)
	for i := range m.h {
		for j := range m.w {
			if visited[Point{j, i}] || m.stars[i*m.w+j] == StarNone {
				continue
			}
			cluster := m.dfs(j, i, m.stars[i*m.w+j], visited)
			if len(cluster) > 1 {
				for _, c := range cluster {
					visited[c] = true
				}
				child := m.Clone()
				child.clear = cluster
				for _, c := range cluster {
					child.stars[c.y*m.w+c.x] = StarNone
				}
				child.Tidy()
				child.score = m.score + child.ClearScore()
				m.childrens = append(m.childrens, child)
			}
		}
	}
	// 打乱顺序，以便通过重试机制尝试不同路径
	rand.Shuffle(len(m.childrens), func(i, j int) {
		m.childrens[i], m.childrens[j] = m.childrens[j], m.childrens[i]
	})
}

func (m *Map) RemoveFirstChildren() {
	if len(m.childrens) == 0 {
		return
	}
	m.childrens = m.childrens[1:]
	// 释放空切片的引用，以便垃圾回收
	if len(m.childrens) == 0 {
		m.childrens = nil
	}
}

// Tidy 对地图进行整理，先向下整理，再向左整理
func (m *Map) Tidy() {
	m.tidyDown()
	m.tidyLeft()
}

// tidyDown 将每列的星星向下移动，把空白位置移到顶部
func (m *Map) tidyDown() {
	for col := int8(0); col < m.w; col++ {
		// 用于记录当前列非空星星的目标位置
		destRow := m.h - 1
		// 从下往上遍历列
		for row := m.h - 1; row >= 0; row-- {
			if m.stars[row*m.w+col] != StarNone {
				// 将非空星星移动到目标位置
				m.stars[destRow*m.w+col] = m.stars[row*m.w+col]
				if destRow != row {
					// 原位置置空
					m.stars[row*m.w+col] = StarNone
				}
				destRow--
			}
		}
		// 将顶部剩余位置置空
		for ; destRow >= 0; destRow-- {
			m.stars[destRow*m.w+col] = StarNone
		}
	}
}

// tidyLeft 将每列的星星向左移动，把空白列移到右侧
func (m *Map) tidyLeft() {
	// 用于记录非空列的目标位置
	destCol := int8(0)
	for col := int8(0); col < m.w; col++ {
		isEmpty := true
		// 检查当前列是否为空
		for row := int8(0); row < m.h; row++ {
			if m.stars[row*m.w+col] != StarNone {
				isEmpty = false
				break
			}
		}
		if !isEmpty {
			if destCol != col {
				// 将非空列移动到目标位置
				for row := int8(0); row < m.h; row++ {
					m.stars[row*m.w+destCol] = m.stars[row*m.w+col]
					m.stars[row*m.w+col] = StarNone
				}
			}
			destCol++
		}
	}
	// 将右侧剩余列置空
	for ; destCol < m.w; destCol++ {
		for row := int8(0); row < m.h; row++ {
			m.stars[row*m.w+destCol] = StarNone
		}
	}
}

func (m *Map) dfs(x, y int8, c Star, visited map[Point]bool) []Point {
	if x < 0 || x >= m.w || y < 0 || y >= m.h || visited[Point{x, y}] || m.stars[y*m.w+x] != c {
		return nil
	}
	visited[Point{x, y}] = true
	ret := []Point{{x, y}}
	ret = append(ret, m.dfs(x+1, y, c, visited)...)
	ret = append(ret, m.dfs(x-1, y, c, visited)...)
	ret = append(ret, m.dfs(x, y+1, c, visited)...)
	ret = append(ret, m.dfs(x, y-1, c, visited)...)
	return ret
}

func (m *Map) Score() uint16 {
	return m.score
}

func (m *Map) TotalScore() uint16 {
	return m.score + m.RemainScore()
}

func (m *Map) ClearCount() uint16 {
	return uint16(len(m.clear))
}

func (m *Map) ClearScore() uint16 {
	n := m.ClearCount()
	return uint16(5 * n * n)
}

func (m *Map) RemainCount() uint16 {
	n := uint16(0)
	for i := range m.h {
		for j := range m.w {
			if m.stars[i*m.w+j] != StarNone {
				n++
			}
		}
	}
	return n
}

func (m *Map) RemainScore() uint16 {
	n := m.RemainCount()
	if n > 10 {
		return 0
	}
	return 2000 - 20*n*n
}

func (m *Map) Parent() *Map {
	return m.parent
}

func NewMap(sizes ...int8) *Map {
	w, h := int8(10), int8(10)
	if len(sizes) > 0 {
		w = sizes[0]
	}
	if len(sizes) > 1 {
		h = sizes[1]
	}
	m := &Map{w: w, h: h, stars: make([]Star, w*h)}
	return m
}
